package J.算法.回溯算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class _17电话号码的字母组合 {

    List<String> res = new ArrayList<>();
    String choise = "";

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0){
            return res;
        }
        HashMap<Integer,String> map = new HashMap<>();
        map.put(2,"abc");
        map.put(3,"def");
        map.put(4,"ghi");
        map.put(5,"jkl");
        map.put(6,"mno");
        map.put(7,"pqrs");
        map.put(8,"tuv");
        map.put(9,"wxyz");

        backtrace(map,digits.toCharArray(),0);
        return res;


    }

    /**
     *
     * @param map
     * @param digits
     * @param index 本次递归再选择数组里的位置
     */
    public void backtrace(HashMap<Integer,String> map,char[] digits,int index){
        if (index == digits.length){
            res.add(choise);
            return;
        }

        int num = digits[index]-'0';
        String mapping = map.get(num);
        for (int i = 0; i < mapping.length(); i++) {
            choise += mapping.charAt(i);
            backtrace(map,digits,index+1);
            choise = choise.substring(0,choise.length()-1);

        }

    }

}
